1   /*
2    * Copyright (C) 2011 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.util.concurrent;
18  
19  import com.google.common.annotations.GwtCompatible;
20  import com.google.common.annotations.GwtIncompatible;
21  import com.google.common.collect.ImmutableMap;
22  import com.google.common.collect.Sets;
23  import com.google.common.testing.NullPointerTester;
24  
25  import junit.framework.TestCase;
26  
27  import java.util.Map;
28  import java.util.Random;
29  import java.util.Set;
30  import java.util.concurrent.ExecutorService;
31  import java.util.concurrent.Executors;
32  import java.util.concurrent.TimeUnit;
33  import java.util.concurrent.atomic.AtomicLong;
34  
35  /**
36   * Tests for {@link AtomicLongMap}.
37   *
38   * @author mike nonemacher
39   */
40  @GwtCompatible(emulated = true)
41  public class AtomicLongMapTest extends TestCase {
42    private static final int ITERATIONS = 100;
43    private static final int MAX_ADDEND = 100;
44  
45    private Random random = new Random(301);
46  
47    @GwtIncompatible("NullPointerTester")
48    public void testNulls() {
49      NullPointerTester tester = new NullPointerTester();
50      tester.testAllPublicConstructors(AtomicLongMap.class);
51      tester.testAllPublicStaticMethods(AtomicLongMap.class);
52      AtomicLongMap<Object> map = AtomicLongMap.create();
53      tester.testAllPublicInstanceMethods(map);
54    }
55  
56    public void testCreate_map() {
57      Map<String, Long> in = ImmutableMap.of("1", 1L, "2", 2L, "3", 3L);
58      AtomicLongMap<String> map = AtomicLongMap.create(in);
59      assertFalse(map.isEmpty());
60      assertSame(3, map.size());
61      assertTrue(map.containsKey("1"));
62      assertTrue(map.containsKey("2"));
63      assertTrue(map.containsKey("3"));
64      assertEquals(1L, map.get("1"));
65      assertEquals(2L, map.get("2"));
66      assertEquals(3L, map.get("3"));
67    }
68  
69    public void testIncrementAndGet() {
70      AtomicLongMap<String> map = AtomicLongMap.create();
71      String key = "key";
72      for (int i = 0; i < ITERATIONS; i++) {
73        long before = map.get(key);
74        long result = map.incrementAndGet(key);
75        long after = map.get(key);
76        assertEquals(before + 1, after);
77        assertEquals(after, result);
78      }
79      assertEquals(1, map.size());
80      assertTrue(!map.isEmpty());
81      assertTrue(map.containsKey(key));
82      assertEquals(ITERATIONS, (int) map.get(key));
83    }
84  
85    public void testIncrementAndGet_zero() {
86      AtomicLongMap<String> map = AtomicLongMap.create();
87      String key = "key";
88      assertEquals(0L, map.get(key));
89      assertFalse(map.containsKey(key));
90  
91      assertEquals(1L, map.incrementAndGet(key));
92      assertEquals(1L, map.get(key));
93  
94      assertEquals(0L, map.decrementAndGet(key));
95      assertEquals(0L, map.get(key));
96      assertTrue(map.containsKey(key));
97  
98      assertEquals(1L, map.incrementAndGet(key));
99      assertEquals(1L, map.get(key));
100   }
101 
102   public void testGetAndIncrement() {
103     AtomicLongMap<String> map = AtomicLongMap.create();
104     String key = "key";
105     for (int i = 0; i < ITERATIONS; i++) {
106       long before = map.get(key);
107       long result = map.getAndIncrement(key);
108       long after = map.get(key);
109       assertEquals(before + 1, after);
110       assertEquals(before, result);
111     }
112     assertEquals(1, map.size());
113     assertTrue(!map.isEmpty());
114     assertTrue(map.containsKey(key));
115     assertEquals(ITERATIONS, (int) map.get(key));
116   }
117 
118   public void testGetAndIncrement_zero() {
119     AtomicLongMap<String> map = AtomicLongMap.create();
120     String key = "key";
121     assertEquals(0L, map.get(key));
122     assertFalse(map.containsKey(key));
123 
124     assertEquals(0L, map.getAndIncrement(key));
125     assertEquals(1L, map.get(key));
126 
127     assertEquals(1L, map.getAndDecrement(key));
128     assertEquals(0L, map.get(key));
129     assertTrue(map.containsKey(key));
130 
131     assertEquals(0L, map.getAndIncrement(key));
132     assertEquals(1L, map.get(key));
133   }
134 
135   public void testDecrementAndGet() {
136     AtomicLongMap<String> map = AtomicLongMap.create();
137     String key = "key";
138     for (int i = 0; i < ITERATIONS; i++) {
139       long before = map.get(key);
140       long result = map.decrementAndGet(key);
141       long after = map.get(key);
142       assertEquals(before - 1, after);
143       assertEquals(after, result);
144     }
145     assertEquals(1, map.size());
146     assertTrue(!map.isEmpty());
147     assertTrue(map.containsKey(key));
148     assertEquals(-1 * ITERATIONS, (int) map.get(key));
149   }
150 
151   public void testDecrementAndGet_zero() {
152     AtomicLongMap<String> map = AtomicLongMap.create();
153     String key = "key";
154     assertEquals(0L, map.get(key));
155     assertFalse(map.containsKey(key));
156 
157     assertEquals(-1L, map.decrementAndGet(key));
158     assertEquals(-1L, map.get(key));
159 
160     assertEquals(0L, map.incrementAndGet(key));
161     assertEquals(0L, map.get(key));
162     assertTrue(map.containsKey(key));
163 
164     assertEquals(-1L, map.decrementAndGet(key));
165     assertEquals(-1L, map.get(key));
166   }
167 
168   public void testGetAndDecrement() {
169     AtomicLongMap<String> map = AtomicLongMap.create();
170     String key = "key";
171     for (int i = 0; i < ITERATIONS; i++) {
172       long before = map.get(key);
173       long result = map.getAndDecrement(key);
174       long after = map.get(key);
175       assertEquals(before - 1, after);
176       assertEquals(before, result);
177     }
178     assertEquals(1, map.size());
179     assertTrue(!map.isEmpty());
180     assertTrue(map.containsKey(key));
181     assertEquals(-1 * ITERATIONS, (int) map.get(key));
182   }
183 
184   public void testGetAndDecrement_zero() {
185     AtomicLongMap<String> map = AtomicLongMap.create();
186     String key = "key";
187     assertEquals(0L, map.get(key));
188     assertFalse(map.containsKey(key));
189 
190     assertEquals(0L, map.getAndDecrement(key));
191     assertEquals(-1L, map.get(key));
192 
193     assertEquals(-1L, map.getAndIncrement(key));
194     assertEquals(0L, map.get(key));
195     assertTrue(map.containsKey(key));
196 
197     assertEquals(0L, map.getAndDecrement(key));
198     assertEquals(-1L, map.get(key));
199   }
200 
201   public void testAddAndGet() {
202     AtomicLongMap<String> map = AtomicLongMap.create();
203     String key = "key";
204     long addend = random.nextInt(MAX_ADDEND);
205     for (int i = 0; i < ITERATIONS; i++) {
206       long before = map.get(key);
207       long result = map.addAndGet(key, addend);
208       long after = map.get(key);
209       assertEquals(before + addend, after);
210       assertEquals(after, result);
211       addend = after;
212     }
213     assertEquals(1, map.size());
214     assertTrue(!map.isEmpty());
215     assertTrue(map.containsKey(key));
216   }
217 
218   public void testAddAndGet_zero() {
219     AtomicLongMap<String> map = AtomicLongMap.create();
220     String key = "key";
221     long value = random.nextInt(MAX_ADDEND);
222     assertEquals(0L, map.get(key));
223     assertFalse(map.containsKey(key));
224 
225     assertEquals(value, map.addAndGet(key, value));
226     assertEquals(value, map.get(key));
227 
228     assertEquals(0L, map.addAndGet(key, -1 * value));
229     assertEquals(0L, map.get(key));
230     assertTrue(map.containsKey(key));
231 
232     assertEquals(value, map.addAndGet(key, value));
233     assertEquals(value, map.get(key));
234   }
235 
236   public void testGetAndAdd() {
237     AtomicLongMap<String> map = AtomicLongMap.create();
238     String key = "key";
239     long addend = random.nextInt(MAX_ADDEND);
240     for (int i = 0; i < ITERATIONS; i++) {
241       long before = map.get(key);
242       long result = map.getAndAdd(key, addend);
243       long after = map.get(key);
244       assertEquals(before + addend, after);
245       assertEquals(before, result);
246       addend = after;
247     }
248     assertEquals(1, map.size());
249     assertTrue(!map.isEmpty());
250     assertTrue(map.containsKey(key));
251   }
252 
253   public void testGetAndAdd_zero() {
254     AtomicLongMap<String> map = AtomicLongMap.create();
255     String key = "key";
256     long value = random.nextInt(MAX_ADDEND);
257     assertEquals(0L, map.get(key));
258     assertFalse(map.containsKey(key));
259 
260     assertEquals(0L, map.getAndAdd(key, value));
261     assertEquals(value, map.get(key));
262 
263     assertEquals(value, map.getAndAdd(key, -1 * value));
264     assertEquals(0L, map.get(key));
265     assertTrue(map.containsKey(key));
266 
267     assertEquals(0L, map.getAndAdd(key, value));
268     assertEquals(value, map.get(key));
269   }
270 
271   public void testPut() {
272     AtomicLongMap<String> map = AtomicLongMap.create();
273     String key = "key";
274     long newValue = random.nextInt(MAX_ADDEND);
275     for (int i = 0; i < ITERATIONS; i++) {
276       long before = map.get(key);
277       long result = map.put(key, newValue);
278       long after = map.get(key);
279       assertEquals(newValue, after);
280       assertEquals(before, result);
281       newValue += newValue;
282     }
283     assertEquals(1, map.size());
284     assertTrue(!map.isEmpty());
285     assertTrue(map.containsKey(key));
286   }
287 
288   public void testPut_zero() {
289     AtomicLongMap<String> map = AtomicLongMap.create();
290     String key = "key";
291     long value = random.nextInt(MAX_ADDEND);
292     assertEquals(0L, map.get(key));
293     assertFalse(map.containsKey(key));
294 
295     assertEquals(0L, map.put(key, value));
296     assertEquals(value, map.get(key));
297 
298     assertEquals(value, map.put(key, 0L));
299     assertEquals(0L, map.get(key));
300     assertTrue(map.containsKey(key));
301 
302     assertEquals(0L, map.put(key, value));
303     assertEquals(value, map.get(key));
304   }
305 
306   public void testPutAll() {
307     Map<String, Long> in = ImmutableMap.of("1", 1L, "2", 2L, "3", 3L);
308     AtomicLongMap<String> map = AtomicLongMap.create();
309     assertTrue(map.isEmpty());
310     assertSame(0, map.size());
311     assertFalse(map.containsKey("1"));
312     assertFalse(map.containsKey("2"));
313     assertFalse(map.containsKey("3"));
314     assertEquals(0L, map.get("1"));
315     assertEquals(0L, map.get("2"));
316     assertEquals(0L, map.get("3"));
317 
318     map.putAll(in);
319     assertFalse(map.isEmpty());
320     assertSame(3, map.size());
321     assertTrue(map.containsKey("1"));
322     assertTrue(map.containsKey("2"));
323     assertTrue(map.containsKey("3"));
324     assertEquals(1L, map.get("1"));
325     assertEquals(2L, map.get("2"));
326     assertEquals(3L, map.get("3"));
327   }
328 
329   public void testPutIfAbsent() {
330     AtomicLongMap<String> map = AtomicLongMap.create();
331     String key = "key";
332     long newValue = random.nextInt(MAX_ADDEND);
333     for (int i = 0; i < ITERATIONS; i++) {
334       long before = map.get(key);
335       long result = map.putIfAbsent(key, newValue);
336       long after = map.get(key);
337       assertEquals(before, result);
338       assertEquals(before == 0 ? newValue : before, after);
339 
340       map.remove(key);
341       before = map.get(key);
342       result = map.putIfAbsent(key, newValue);
343       after = map.get(key);
344       assertEquals(0, before);
345       assertEquals(before, result);
346       assertEquals(newValue, after);
347 
348       map.put(key, 0L);
349       before = map.get(key);
350       result = map.putIfAbsent(key, newValue);
351       after = map.get(key);
352       assertEquals(0, before);
353       assertEquals(before, result);
354       assertEquals(newValue, after);
355 
356       newValue += newValue;
357     }
358     assertEquals(1, map.size());
359     assertTrue(!map.isEmpty());
360     assertTrue(map.containsKey(key));
361   }
362 
363   public void testPutIfAbsent_zero() {
364     AtomicLongMap<String> map = AtomicLongMap.create();
365     String key = "key";
366     long value = random.nextInt(MAX_ADDEND);
367     assertEquals(0L, map.get(key));
368     assertFalse(map.containsKey(key));
369 
370     assertEquals(0L, map.putIfAbsent(key, value));
371     assertEquals(value, map.get(key));
372 
373     assertEquals(value, map.put(key, 0L));
374     assertEquals(0L, map.get(key));
375     assertTrue(map.containsKey(key));
376 
377     assertEquals(0L, map.putIfAbsent(key, value));
378     assertEquals(value, map.get(key));
379   }
380 
381   public void testReplace() {
382     AtomicLongMap<String> map = AtomicLongMap.create();
383     String key = "key";
384     long newValue = random.nextInt(MAX_ADDEND);
385     for (int i = 0; i < ITERATIONS; i++) {
386       long before = map.get(key);
387       assertFalse(map.replace(key, before + 1, newValue + 1));
388       assertFalse(map.replace(key, before - 1, newValue - 1));
389       assertTrue(map.replace(key, before, newValue));
390       long after = map.get(key);
391       assertEquals(newValue, after);
392       newValue += newValue;
393     }
394     assertEquals(1, map.size());
395     assertTrue(!map.isEmpty());
396     assertTrue(map.containsKey(key));
397   }
398 
399   public void testReplace_zero() {
400     AtomicLongMap<String> map = AtomicLongMap.create();
401     String key = "key";
402     long value = random.nextInt(MAX_ADDEND);
403     assertEquals(0L, map.get(key));
404     assertFalse(map.containsKey(key));
405 
406     assertTrue(map.replace(key, 0L, value));
407     assertEquals(value, map.get(key));
408 
409     assertTrue(map.replace(key, value, 0L));
410     assertEquals(0L, map.get(key));
411     assertTrue(map.containsKey(key));
412 
413     assertTrue(map.replace(key, 0L, value));
414     assertEquals(value, map.get(key));
415   }
416 
417   public void testRemove() {
418     AtomicLongMap<String> map = AtomicLongMap.create();
419     String key = "key";
420     assertEquals(0, map.size());
421     assertTrue(map.isEmpty());
422     assertEquals(0L, map.remove(key));
423 
424     long newValue = random.nextInt(MAX_ADDEND);
425     for (int i = 0; i < ITERATIONS; i++) {
426       map.put(key, newValue);
427       assertTrue(map.containsKey(key));
428 
429       long before = map.get(key);
430       long result = map.remove(key);
431       long after = map.get(key);
432       assertFalse(map.containsKey(key));
433       assertEquals(before, result);
434       assertEquals(0L, after);
435       newValue += newValue;
436     }
437     assertEquals(0, map.size());
438     assertTrue(map.isEmpty());
439   }
440 
441   public void testRemove_zero() {
442     AtomicLongMap<String> map = AtomicLongMap.create();
443     String key = "key";
444     assertEquals(0L, map.get(key));
445     assertFalse(map.containsKey(key));
446 
447     assertEquals(0L, map.remove(key));
448     assertEquals(0L, map.get(key));
449     assertFalse(map.containsKey(key));
450 
451     assertEquals(0L, map.put(key, 0L));
452     assertEquals(0L, map.get(key));
453     assertTrue(map.containsKey(key));
454 
455     assertEquals(0L, map.remove(key));
456     assertEquals(0L, map.get(key));
457     assertFalse(map.containsKey(key));
458   }
459 
460   public void testRemoveValue() {
461     AtomicLongMap<String> map = AtomicLongMap.create();
462     String key = "key";
463     assertEquals(0, map.size());
464     assertTrue(map.isEmpty());
465     assertFalse(map.remove(key, 0L));
466 
467     long newValue = random.nextInt(MAX_ADDEND);
468     for (int i = 0; i < ITERATIONS; i++) {
469       map.put(key, newValue);
470       assertTrue(map.containsKey(key));
471 
472       long before = map.get(key);
473       assertFalse(map.remove(key, newValue + 1));
474       assertFalse(map.remove(key, newValue - 1));
475       assertTrue(map.remove(key, newValue));
476       long after = map.get(key);
477       assertFalse(map.containsKey(key));
478       assertEquals(0L, after);
479       newValue += newValue;
480     }
481     assertEquals(0, map.size());
482     assertTrue(map.isEmpty());
483   }
484 
485   public void testRemoveValue_zero() {
486     AtomicLongMap<String> map = AtomicLongMap.create();
487     String key = "key";
488     assertEquals(0L, map.get(key));
489     assertFalse(map.containsKey(key));
490 
491     assertFalse(map.remove(key, 0L));
492     assertEquals(0L, map.get(key));
493     assertFalse(map.containsKey(key));
494 
495     assertEquals(0L, map.put(key, 0L));
496     assertEquals(0L, map.get(key));
497     assertTrue(map.containsKey(key));
498 
499     assertTrue(map.remove(key, 0L));
500     assertEquals(0L, map.get(key));
501     assertFalse(map.containsKey(key));
502   }
503 
504   public void testRemoveZeros() {
505     AtomicLongMap<Object> map = AtomicLongMap.create();
506     Set<Object> nonZeroKeys = Sets.newHashSet();
507     for (int i = 0; i < ITERATIONS; i++) {
508       Object key = new Object();
509       long value = i % 2;
510       map.put(key, value);
511       if (value != 0L) {
512         nonZeroKeys.add(key);
513       }
514     }
515     assertEquals(ITERATIONS, map.size());
516     assertTrue(map.asMap().containsValue(0L));
517 
518     map.removeAllZeros();
519     assertFalse(map.asMap().containsValue(0L));
520     assertEquals(ITERATIONS / 2, map.size());
521     assertEquals(nonZeroKeys, map.asMap().keySet());
522   }
523 
524   public void testClear() {
525     AtomicLongMap<Object> map = AtomicLongMap.create();
526     for (int i = 0; i < ITERATIONS; i++) {
527       map.put(new Object(), i);
528     }
529     assertEquals(ITERATIONS, map.size());
530 
531     map.clear();
532     assertEquals(0, map.size());
533     assertTrue(map.isEmpty());
534   }
535 
536   public void testSum() {
537     AtomicLongMap<Object> map = AtomicLongMap.create();
538     long sum = 0;
539     for (int i = 0; i < ITERATIONS; i++) {
540       map.put(new Object(), i);
541       sum += i;
542     }
543     assertEquals(ITERATIONS, map.size());
544     assertEquals(sum, map.sum());
545   }
546 
547   public void testEmpty() {
548     AtomicLongMap<String> map = AtomicLongMap.create();
549     assertEquals(0L, map.get("a"));
550     assertEquals(0, map.size());
551     assertTrue(map.isEmpty());
552     assertFalse(map.remove("a", 1L));
553     assertFalse(map.remove("a", 0L));
554     assertFalse(map.replace("a", 1L, 0L));
555   }
556 
557   @GwtIncompatible("threads")
558   public void testModify_basher() throws InterruptedException {
559     int nTasks = 3000;
560     int nThreads = 100;
561     final int getsPerTask = 1000;
562     final int deltaRange = 10000;
563     final String key = "key";
564 
565     final AtomicLong sum = new AtomicLong();
566     final AtomicLongMap<String> map = AtomicLongMap.create();
567 
568     ExecutorService threadPool = Executors.newFixedThreadPool(nThreads);
569     for (int i = 0; i < nTasks; i++) {
570       threadPool.submit(new Runnable() {
571         @Override public void run() {
572           int threadSum = 0;
573           for (int j = 0; j < getsPerTask; j++) {
574             long delta = random.nextInt(deltaRange);
575             int behavior = random.nextInt(10);
576             switch (behavior) {
577               case 0:
578                 map.incrementAndGet(key);
579                 threadSum++;
580                 break;
581               case 1:
582                 map.decrementAndGet(key);
583                 threadSum--;
584                 break;
585               case 2:
586                 map.addAndGet(key, delta);
587                 threadSum += delta;
588                 break;
589               case 3:
590                 map.getAndIncrement(key);
591                 threadSum++;
592                 break;
593               case 4:
594                 map.getAndDecrement(key);
595                 threadSum--;
596                 break;
597               case 5:
598                 map.getAndAdd(key, delta);
599                 threadSum += delta;
600                 break;
601               case 6:
602                 long oldValue = map.put(key, delta);
603                 threadSum += delta - oldValue;
604                 break;
605               case 7:
606                 oldValue = map.get(key);
607                 if (map.replace(key, oldValue, delta)) {
608                   threadSum += delta - oldValue;
609                 }
610                 break;
611               case 8:
612                 oldValue = map.remove(key);
613                 threadSum -= oldValue;
614                 break;
615               case 9:
616                 oldValue = map.get(key);
617                 if (map.remove(key, oldValue)) {
618                   threadSum -= oldValue;
619                 }
620                 break;
621               default:
622                 throw new AssertionError();
623             }
624           }
625           sum.addAndGet(threadSum);
626         }
627       });
628     }
629 
630     threadPool.shutdown();
631     assertTrue(threadPool.awaitTermination(300, TimeUnit.SECONDS));
632 
633     assertEquals(sum.get(), map.get(key));
634   }
635 }